package airthmetic.exercise.hash;

import java.util.Arrays;
import java.util.HashMap;

public class _242_有效的字母异位词 {
    // 思路：设计一致性hash算法(散列函数) 让所有出现的字符映射到一个散列数组上，然后根据数组上元素值的数量是否为0判断
    public static boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()){
            return false;
        }

        int[] array = new int[26];
        for (int i=0; i<s.length(); i++){
            // 此处的 s.charAt(i) - 'a' 为我们一致性hash算法
            array[s.charAt(i) - 'a']++; 
            array[t.charAt(i) - 'a']--;
        }

        for(int i=0; i<array.length; i++){
            if(array[i] != 0){
                return false;
            }
        }
        return true;
    }

    // 排序写法
    public static boolean isAnagram2(String s, String t) {
        if (s == null || t == null || s.length() != t.length()){
            return false;
        }
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        return Arrays.equals(sChars,tChars);
    }

    // hashMap写法
    public static boolean isAnagram3(String s, String t) {
        if (s == null || t == null || s.length() != t.length()){
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c) + 1);
            }else{
                map.put(c,1);
            }
        }

        for (int i=0; i<t.length(); i++){
            char c = t.charAt(i);
            if(!map.containsKey(c)){
                return false;
            }else{
                int num = map.get(c)  - 1;
                if (num < 0){
                    return false;
                }
                map.put(c,num);
            }
        }

        return true;
    }

    public static void main(String[] args) {
        String s = "qaqee";
        String t = "eeqaq";
        System.out.println(isAnagram(s,t));
        System.out.println(isAnagram2(s,t));
        System.out.println(isAnagram3(s,t));
    }
}
